This invention relates to an apparatus and method for the manipulation and coordinate transformation of multidimensional data.
Many of the medical imaging modalities, such as CT, MR, PET and SPECT, produce three-dimensional representations of the anatomy or physiology under study. However, current medical practice is to review this data in a two-dimensional fashion, typically as a large number (20 to 100) of parallel slices arrayed side-by-side. The physician is called upon to mentally integrate these slices into an understanding of the actual locations of objects within the patient. Radiologists, after much practice, are able to do this, but the referring physician, with much less practice, may have difficulty.
The disclosed invention allows the presentation of the diagnostic imaging information to the physician in such a way that he can directly appreciate the full spatial and contrast range of the data and interact with this information to optimize his understanding of the subject.
The problem of representing 3-D objects is not unique to medicine. The field of CAD/CAM has done considerable work in computer representation of 3-D objects and some of these techniques have been applied to medicine.
In general, objects in CAD/CAM are represented by surfaces and are assumed to be of a homogeneous composition. This technique is inappropriate for representing medical imagery since it eliminates all contrast information in the data by preselecting a surface. The only medical application that may be appropriate for these "surface rendering" techniques is for the presentation of bone structures to orthopedic surgeons. Even for this application, the surface rendering techniques are flawed since the a priori discrimination of bone from non-bone can be difficult where osteoporosis has reduced the bone density or where partial volume effects reduce the bone-tissue contrast.
Several groups have recognized the value of preserving the contrast or density information in the volume data set and the value of presenting this information as well as the 3-D representation of the subject.
Systems based on the concept of encoding the 3-D information into an Octree, a linked hierarchical data structure, and processing the Octree into a (2-D) displayable format have been built, see U.S. Pat. No. 4,694,404, incorporated herein by reference. There are two chief disadvantages with the Octree approach however. Firstly, the Octree processing engine is currently very expensive. Secondly, the image data must be converted from their original voxel format to an Octree format. This operation need only be done once per volume data set, but is very time consuming, requiring hours or substantial fractions of an hour on a general purpose minicomputer.
A more straightforward approach has also been used. In this approach, the system stores volume data in voxel form and maps the 3-D object into a 2-D space with a "back-to-front" or "painters algorithm". This back-to-front algorithm entails reading the 3-D volume in an order such that pixels which are being written into the 2-D display space are always nearer to the observer than previously written pixels and thus obscure those previous pixels. Thus, the analogy to a painter, where fresh paint obscures older paint. The exact reading order of 3-D voxels will be a function of observer perspective (the orientation of the object).
The advantages of this approach are that no "z-buffer" is required and the data are retained in their original (voxel) format. A z-buffer is required whenever the back-to-front read-out order cannot be preserved and is the way that objects are made to superimpose properly. A z-buffer algorithm states that if a new pixel is to be written in observer space, its depth with respect to the observer (z dimension) determines whether it is written or discarded. If the new pixel is nearer the observer than any old pixel, it overwrites (obscures) the old pixel. Otherwise the new pixel is behind the old pixel and is discarded. The back-to-front approach eliminates this decision, since the new pixel is always nearer the observer and always overwrites the old pixel.
While the back-to-front approach represents an implementation advantage it also limits the flexibility of the transform process. Specifically, it is often required to transform different portions of the volume data set differently, where no back-to-front order could be maintained.
The present invention allows the rapid and efficient transformation of different portions of the data set. This allows independent transformation of different objects and/or portions of objects. In addition, it allows costly and inherently slow multiplier circuits to be avoided in the transform process.
Part of the present invention is a means and process for performing the z-buffering and/or the coordinate transformation in parallel fashion. The utility of this technique is not limited to just medical imaging.
In general, some representation of a 3 dimensional object or scene is processed within a 3-D transformation engine. The method of representation can vary, from coordinates of polygon vertices, as is commonly done in CAD/CAM, or as voxels, 3-D picture elements, or as Octree nodes. The 3-D transformation engine performs the transformations that transform from the object's space to the observer's space. However, the output of the 3-D engine is usually not ordered in any way, and does not account for hidden surface removal.
The 3-D engine outputs a serial stream of 3-D coordinates and a value or values associated with each coordinate. These 3-D coordinates are observer space position (x and y) and depth (z) relative to the observer. The value(s) are some measure of the object at that coordinate, such as composition, color, density, temperature, etc. What will be visible to the observer are only those features in the object that are nearest the observer; features behind other features are obscured. A z-Buffer is employed to perform this hidden feature or hidden surface operation.
The z-buffer algorithm is well-known and relatively straightforward to implement, but it inherently presents a bottleneck. For every new coordinate, the old depth must be retrieved from a depth memory, the old and new depths must be compared, and the new depth and value might have to be written into the respective memories. This means that three operations have to be performed in the time it takes to generate one new coordinate n-tuple, an n-tuple being the n coordinates necessary to describe an n-dimensional space. By implementing this process in a parallel form, the present invention avoids this bottleneck. Additionally, the coordinate transformation can also be performed in parallel, further speeding the process.
The result of the z-buffer operation is that the observer sees the surfaces of the nearest objects. In some situations, however, this may not be the most desirable presentation. In radiation therapy, it is important to know what objects lie both in front of the object of interest and behind it. The traditional surface presentation can often not provide this information. For this application, it is more desirable to present a "translucency" view, where all the objects in the scene are visible, but superimposed. The best analogy to this view is a conventional radiograph, which superimposes all structures. The present invention allows the z-buffers to be operated in two modes: the normal mode and a "radiographic" mode where a translucency view is presented instead of the normal surface view.